{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of All Odd Length Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumOddLengthSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有奇数长度子数组的和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组&nbsp;<code>arr</code>&nbsp;，请你计算所有可能的奇数长度子数组的和。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 定义为原数组中的一个连续子序列。</p>\n",
    "\n",
    "<p>请你返回 <code>arr</code>&nbsp;中 <strong>所有奇数长度子数组的和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,4,2,5,3]\n",
    "<strong>输出：</strong>58\n",
    "<strong>解释：</strong>所有奇数长度子数组和它们的和为：\n",
    "[1] = 1\n",
    "[4] = 4\n",
    "[2] = 2\n",
    "[5] = 5\n",
    "[3] = 3\n",
    "[1,4,2] = 7\n",
    "[4,2,5] = 11\n",
    "[2,5,3] = 10\n",
    "[1,4,2,5,3] = 15\n",
    "我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [10,11,12]\n",
    "<strong>输出：</strong>66\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<p>你可以设计一个 O(n) 时间复杂度的算法解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-all-odd-length-subarrays](https://leetcode.cn/problems/sum-of-all-odd-length-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-all-odd-length-subarrays](https://leetcode.cn/problems/sum-of-all-odd-length-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,2,5,3]', '[1,2]', '[10,11,12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        leng = 1\n",
    "        n = len(arr)\n",
    "        res = 0\n",
    "        while(leng <= n):\n",
    "            tmp = 0\n",
    "            for i in range(n-leng+1):\n",
    "                tmp += sum(arr[i:i+leng])\n",
    "            res += tmp\n",
    "            leng += 2\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        \n",
    "        length = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(length):\n",
    "            left = i + 1\n",
    "            right = length - i\n",
    "            l_even = (left+1) // 2\n",
    "            l_odd = left // 2\n",
    "            r_even = (right+1) // 2\n",
    "            r_odd = right // 2\n",
    "            ans += (l_even*r_even + l_odd*r_odd) * arr[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "        current_sub_array_len = 1\n",
    "        odd_sum = 0\n",
    "        while current_sub_array_len <= len(arr):\n",
    "            start = 0\n",
    "            end = start + current_sub_array_len\n",
    "            while end <= len(arr):\n",
    "                odd_sum += sum(arr[start:end])\n",
    "                start +=1\n",
    "                end = start + current_sub_array_len\n",
    "            current_sub_array_len += 2\n",
    "\n",
    "        return odd_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(1,len(arr)+1,2):\n",
    "            for j in range(len(arr)-i+1):\n",
    "                res+=sum(arr[j:j+i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def sumOddLengthSubarrays(self, arr):\n",
    "        ret = 0\n",
    "        for i in range(len(arr)):\n",
    "            bei = 0\n",
    "            while i+bei < len(arr):\n",
    "                ret += sum(arr[i:i+bei+1])\n",
    "                bei += 2\n",
    "        return ret\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        sums = []\n",
    "        i = 1\n",
    "        for i in range(1,len(arr)+1,2):\n",
    "            childlist = childList(arr,i)\n",
    "            sub_sum = [sum(iterm) for iterm in childlist]\n",
    "            sums = sums + sub_sum\n",
    "        return sum(sums)\n",
    "\n",
    "def childList(arr,length):\n",
    "    childlist = []\n",
    "    for i in range(len(arr)-(length-1)):\n",
    "        temp = arr[i:]\n",
    "        childlist.append(temp[:length])\n",
    "    return childlist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        i = 0\n",
    "        res = []\n",
    "        while 2*i+1 <= l:\n",
    "            t = 2*i+1\n",
    "            j = 0\n",
    "            while j+t<=l:\n",
    "                res.append(arr[j:j+t])\n",
    "                j+=1\n",
    "            i+=1\n",
    "        return sum(map(sum,res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        odd,res, ans = [], [], 0 \n",
    "        for i in range(1, len(arr)+1):\n",
    "            if i % 2 == 1:\n",
    "                odd.append(i)\n",
    "        for i in odd:\n",
    "            # print(i)\n",
    "            for j in range(len(arr)):\n",
    "                if j + i < len(arr) + 1:\n",
    "                    res.append(arr[j:j+i])\n",
    "        for i in res:\n",
    "            ans += sum(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        pre=[0]\n",
    "        for num in arr:\n",
    "            pre.append(pre[-1]+num)\n",
    "        res=0\n",
    "        for l in range(1,n+1,2):\n",
    "            for i in range(0,n+1-l):\n",
    "                res += pre[i+l]-pre[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(arr)\n",
    "        for i in range(1, n + 1):\n",
    "            if i % 2 == 1:\n",
    "                j = 0\n",
    "                while j + i <= n:\n",
    "                    ans += sum(arr[j:j + i])\n",
    "                    j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i = 1\n",
    "        while i <= len(arr):\n",
    "            j = 0\n",
    "            while j + i <= len(arr):\n",
    "                ans += sum(arr[j:j+i])\n",
    "                j += 1\n",
    "            i += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums,initial = 0))\n",
    "        print(s)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if (j-i +1) % 2==1:\n",
    "                    ans += s[j+1] - s[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = 2\n",
    "        end = 2\n",
    "        i = 0\n",
    "        sum1 = sum(arr)\n",
    "        while right < n:\n",
    "            left = 0\n",
    "            for i in range(n - end):\n",
    "                sum1 = sum1 + sum(arr[left:right+1])\n",
    "                left += 1\n",
    "                right += 1\n",
    "                print(sum1)\n",
    "            end += 2\n",
    "            right = end\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        ans = []\n",
    "        for i in range(len(arr)):\n",
    "            ans.append(arr[i])\n",
    "            if i % 2 == 0:\n",
    "                for j in range(i+1,len(arr)):\n",
    "                    if j % 2 == 0:\n",
    "                        ans.append(sum(arr[i:j+1]))\n",
    "            else:\n",
    "                for j in range(i+1,len(arr)):\n",
    "                    if j % 2 == 1:\n",
    "                        ans.append(sum(arr[i:j+1]))\n",
    "        print(ans)\n",
    "        return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        sum1 = 0\n",
    "        i = 1\n",
    "        while i <= n:\n",
    "            for j in range(n + 1 - i):\n",
    "                sum1 += sum(arr[j : j + i])\n",
    "            i += 2\n",
    "        return sum1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        sum = 0\n",
    "        n = len(arr)\n",
    "        for start in range(n):\n",
    "            length = 1\n",
    "            while start + length <= n:\n",
    "                for v in arr[start:start + length]:\n",
    "                    sum += v\n",
    "                length += 2\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOddLengthSubarrays(self, arr: List[int]) -> int:\n",
    "        # 前缀和，在每一个位置都计算以该位置结尾的前缀和\n",
    "        add = [0] * (len(arr) + 1)\n",
    "        ans = 0\n",
    "        for i in range(1, len(arr)+1):\n",
    "            add[i] = add[i-1] + arr[i-1]\n",
    "        # print(add)\n",
    "        for i in range(1, len(add)):\n",
    "            j = 1\n",
    "            while j <= i:\n",
    "                if  (i - j + 1) % 2 == 1:\n",
    "                    # print(i, j, add[i] - add[j-1])\n",
    "                    ans += add[i] - add[j-1]\n",
    "                    j += 2\n",
    "                else:\n",
    "                    j += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
